package com.hdu.other.tanxin;


import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class lc857 {
    class Solution {
        public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
            int len = quality.length;
            Employee[] employees = new Employee[len];
            for (int i = 0; i < len; i++) {
                employees[i] = new Employee((double) wage[i] / quality[i], quality[i]);
            }
            Arrays.sort(employees, Comparator.comparingDouble(o -> o.ratio));
            PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
            double ans = Double.MAX_VALUE;
            int preMinKSum = 0;
            for (int i = 0; i < len; i++) {
                if (pq.size() < k) {
                    pq.offer(employees[i].quality);
                    preMinKSum += employees[i].quality;
                    if (pq.size() == k) {
                        ans = Math.min(ans, preMinKSum * employees[i].ratio);
                    }
                } else {
                    if (employees[i].quality < pq.peek()) {
                        preMinKSum += employees[i].quality - pq.poll();
                        pq.offer(employees[i].quality);
                    }
                    ans = Math.min(ans, preMinKSum * employees[i].ratio);
                }
            }
            return ans;
        }

        class Employee {
            int quality;
            double ratio;

            public Employee(double ratio, int quality) {
                this.ratio = ratio;
                this.quality = quality;
            }
        }
    }
}
